/*
 * Copyright (C), 2015-2018
 * FileName: Solution069
 * Author:   zhao
 * Date:     2018/9/6 14:37
 * Description: 69. x 的平方根
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.hundredone;

/**
 * 〈一句话功能简述〉<br>
 * 〈69. x 的平方根〉
 *
 * @author zhao
 * @date 2018/9/6 14:37
 * @since 1.0.1
 */
public class Solution069 {
  /**************************************
   * 题目
   实现 int sqrt(int x) 函数。

   计算并返回 x 的平方根，其中 x 是非负整数。

   由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

   示例 1:

   输入: 4
   输出: 2
   示例 2:

   输入: 8
   输出: 2
   说明: 8 的平方根是 2.82842...,
   由于返回类型是整数，小数部分将被舍去。
   **************************************/

  /**************************************
   *
   * 想法：
   *      1. 二分法找到平方根小于输入值
   *      2. 调整系数，使最后的值落在一个区间之内
   *                double upper = x * 1.0000005;
   *                double lower = x * 0.9999995;
   * 我的做法：
   *      没做出来，调整系数，会有误差
   *  总结：
   *      思路应该是正确的，使用二分法进行
   *      不要把问题复杂化了，能不用浮点类型就不要使用
   *      可以使用加1进行调节
   * ***********************************/
  public int mySqrt(int x) {
    if (CommonValue.NOT_ANSWER) {
      return better(x);
    }
    if (x == 1) {
      return 1;
    }

    if (x == 3) {
      return 3;
    }
    double upper = x * 1.0000005;
    double lower = x * 0.9999995;

    double preUpTarget = x;
    double preLowerTarget = 0;
    double target = (preUpTarget + preLowerTarget) / 2;

    boolean isNeedStop = false;

    while (!isNeedStop) {
      if (target * target > upper) {
        preUpTarget = target;
        target = (preUpTarget + preLowerTarget) / 2;
      } else if (target * target < lower) {
        preLowerTarget = target;
        target = (preUpTarget + preLowerTarget) / 2;
      } else {
        isNeedStop = true;
      }

    }

    return (int) target;
  }

  /**************************************
   * 比我好的答案
   * 7.22%
   * ***********************************/
  public int better(int x) {
    if (x <= 1) {
      return x;
    }
    int left = 0;
    int right = x;
    while (left < right) {
      // 中间值
      int mid = left + (right - left) / 2;

      // 更新上下界
      if (x / mid >= mid) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }

    return right - 1;
  }

  /**************************************
   * 牛顿逼近法
   *
   * 这道题还有另一种解法，是利用牛顿迭代法，记得高数中好像讲到过这个方法，是用逼近法求方程根的神器，
   * 在这里也可以借用一下，可参见网友Annie Kim's Blog的博客，
   * 因为要求x2 = n的解，令f(x)=x2-n，相当于求解f(x)=0的解，可以求出递推式如下：
   * xi+1=xi - (xi2 - n) / (2xi) = xi - xi / 2 + n / (2xi) = xi / 2 + n / 2xi = (xi + n/xi) / 2
   * ***********************************/
  public int better2(int x) {
    long res = x;
    while (res * res > x) {
      res = (res + x / res) / 2;
    }
    return (int) res;
  }

}
